package oj.oj_160;

import oj.ListNode;

/**
 * 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 */
public class Solution {
    private int sizeOf(ListNode head){
        int count=0;
        for(ListNode cur=head;cur!=null;cur=cur.next){
            count++;
        }
        return count;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int stepA=sizeOf(headA);
        int stepB=sizeOf(headB);
        if(stepA>stepB){
            int step=stepA-stepB;
            for(int i=0;i<step;i++){
                headA=headA.next;
            }
        } else if (stepA<stepB) {
            int step=stepB-stepA;
            for(int i=0;i<step;i++){
                headB=headB.next;
            }
        }else{
            // 相等，不用动
        }
        ListNode curA=headA;
        ListNode curB=headB;
        while(curA!=curB){// 相交情况下的交点 或者 不相交情况下的 null
            curA=curA.next;
            curB=curB.next;
        }
        return curA;
    }
}
